package com.cheng.algorithm.search;

import java.util.Arrays;

/**
 * @User Administrator
 * @Classname InsertValueSearch
 * @Project Data-structure-and-algorithm
 * @Description 插值查找
 * @Author wpcheng
 * @Create 2021-08-16-10:51
 * @Version 1.0
 */
public class InsertValueSearch {
    public static void main(String[] args) {
        int[] arr = new int[100];
        for (int i = 0; i < 100; i++) {
            arr[i] = i + 1;
        }
//        System.out.println(Arrays.toString(arr));
        int i = binarySearch(arr, 0, 99, 102);
        if (i == -1){
            System.out.println("没找到");
        }else {
            System.out.println("查找到下标为："+i+" 的数");
        }
    }
    /**
     *
     * @param arr       数组
     * @param left      左边的索引
     * @param right     右边的索引
     * @param findVal   要查找的数
     * @return  找到返回下标，没找到返回-1
     */
    public static int binarySearch(int[] arr,int left,int right,int findVal){

        if (left > right || arr[left] > findVal || arr[right] < findVal){  //防止mid越界
            return -1;
        }
        int mid  = left + (right + left) * (findVal - arr[left]) / (arr[right] - arr[left]);
        int midVal = arr[mid];
        if (findVal > midVal){
            return binarySearch(arr,mid + 1,right,findVal);
        }else if (findVal < midVal){
            return binarySearch(arr,left,mid - 1,findVal);
        }else {
            return mid;
        }
    }
}
